1. Field of the Invention
This invention relates generally to cryptography, and more particularly, to a method for achieving the establishing of key agreement between two communicating parties.
2. Description of the Related Art
Cryptographic systems ensure the privacy of a message transmitted over an untrusted communication channel, such as intranets, the Internet, the World Wide Web, cellular phones, and cordless phones. A principal purpose for a cryptographic system is to maintain the secrecy of a transmitted message from unauthorized parties, and therefore assuring the sender that the message is only being read by the intended recipient. To preserve such secrecy, a message can be encrypted to a ciphertext by an encryption method, such as private-key encryption, also referred to as symmetric encryption, secret-key encryption, or single-key encryption.
Private key encryption requires both an encryption algorithm and a cryptographic key. The encryption algorithm provides security for a message by making it impractical for an eavesdropper to decrypt the ciphertext back into the plaintext message on the basis of the ciphertext alone. Suitable encryption algorithms for a private key encryption include DES, IDEA, and RC5. The cryptographic key is a selected value which is independent of the plaintext, and controls the encryption algorithm. The encryption algorithm generates an output ciphertext that depends on the specific cryptographic key used at the time, so that a change in the cryptographic key causes the encryption algorithm to generate a different output ciphertext. After a sender has encrypted a plaintext into a ciphertext, the sender transmits the ciphertext to its intended recipient. The recipient then converts the ciphertext back to the plaintext using a decryption algorithm.
The security of a message depends on the secrecy of the cryptographic key used to encrypt the message. Two mechanisms are typically used to allow communicating parties to establish the cryptographic key: (1) key distribution, and (2) key agreement. Key distribution is a mechanism by which one party transfers the actual cryptographic key to another party. Key agreement denotes a protocol whereby two or more parties jointly establish a cryptographic key across an untrusted communication channel without the physical transfer of the cryptographic key. A well-known example of establishing a cryptographic key by establishing a key agreement between multiple parties is the Diffie-Hellman method.
The Diffie-Hellman method is based on the apparent difficulty in computing logarithms over a finite field GF(q) with a prime number q of elements. For two communicating parties 1 and 2, the Diffie-Hellman method uses a key K=a.sup.X1X2 mod q, where "mod" denotes a modulo operation. Modulo is an operation this is similar to the operation of obtaining a remainder in an arithmetic division. In the Diffie-Hellman method, a party i publishes in a public system the value Y.sub.i =a.sup.Xi mod q, where Xi is a private undisclosed value in GF(q). To communicate with a party j, party i obtains a key K.sub.ij by computing K.sub.ij =(Y.sub.j).sup.Xi mod q. Similarly, party j obtains the key K.sub.ij by computing K.sub.ij =(Y.sub.i).sup.Xj mod q. The Diffie-Hellman method is disclosed in U.S. Pat. No. 4,200,770, entitled "Cryptographic Apparatus and Method," issued on Apr. 29, 1980, to Hellman et al.
The drawback of the Diffie-Hellman method is that the computation of the cryptographic key is slow due to the intensive computation of modulo (i.e. mod q) and exponentiation over a finite field GF(q). The combination of the modulo operation and the calculation of the exponential a.sup.X1X2 result in slow performance.
Hence, it is desirable to have a faster protocol for establishing key agreement between multiple communication devices across an untrusted communication channel.